import java.util.List;
import java.util.Scanner;

//最短寻道时间优先
class SSTF{
    public int visit[];
    public int distance[];
    private int nearIndex=0;
    public void sstf(int queue[],int start){
        int nearNum=9999;
        visit=new int[queue.length];
        distance=new int[queue.length];
        for(int i=0;i<queue.length;i++){
            for(int j=0;j<queue.length;j++){
                if(queue[j]!=-1){
                    if(Math.abs(nearNum-start)>Math.abs(queue[j]-start)){
                        nearNum=queue[j];
                        nearIndex=j;
                    }
                }
            }
            visit[i]=nearNum;
            distance[i]=Math.abs(start-visit[i]);
            queue[nearIndex]=-1;
            start=nearNum;
            nearNum=9999;
        }

    }
    public void print(int visit[],int start){
        double sum=0;
        System.out.print("访问序列：");
        for(int i=0;i<visit.length;i++){
            System.out.print(visit[i]+" ");
            sum=Math.abs(visit[i]-start)+sum;
            start=visit[i];
        }
        System.out.println();
        System.out.print("移动距离为：");
        for(int i=0;i<visit.length;i++){
            System.out.print(distance[i]+" ");
        }
        System.out.println();
        System.out.println("经过的磁道总数："+sum);
        System.out.println("平均寻道长度："+sum/visit.length);
    }
}

class FCFS{
    public int visit[];
    public int index=0;
    public int distance[];

    public void fcfs(int queue[],int start){
        visit=new int[queue.length];
        distance=new int[queue.length];
        for(int i=0;i<queue.length;i++){
            distance[i]=Math.abs(start-queue[i]);
            visit[i]=queue[i];
            start=queue[i];
        }
    }
    public void print(int visit[],int start){
        double sum=0;
        System.out.print("访问序列：");
        for(int i=0;i<visit.length;i++){
            System.out.print(visit[i]+" ");
            sum=distance[i]+sum;
        }
        System.out.println();
        System.out.print("移动距离为：");
        for(int i=0;i<visit.length;i++){
            System.out.print(distance[i]+" ");
        }
        System.out.println();
        System.out.println("经过的磁道总数："+sum);
        System.out.println("平均寻道长度："+sum/visit.length);
    }
}

class SCAN{
    public int visit[];
    public int nearIndex=0;
    public int distance[];

    public void scan(int queue[],int start,int direction){
        int nearNum=9999;
        int index=0;
        visit=new int[queue.length];
        distance=new int[queue.length];
        for(int i=0;i<queue.length;i++){
            index=-1;
            for(int j=0;j<queue.length;j++){
                if(queue[j]!=-1){
                    if((direction==1)&&(queue[j]>start)&&(Math.abs(nearNum-start)>Math.abs(queue[j]-start))){
                        nearNum=queue[j];
                        nearIndex=j;
                        index=0;
                    }
                    else if((direction==0)&&(queue[j]<start)&&(Math.abs(nearNum-start)>Math.abs(queue[j]-start))){
                        nearNum=queue[j];
                        nearIndex=j;
                        index=0;
                    }
                }
            }
            if((direction==1)&&(index==-1)){
                direction=0;
                i=i-1;
            }
            else if((direction==0)&&(index==-1)){
                direction=1;
                i=i-1;
            }
            if(index==0){
                visit[i]=nearNum;
                distance[i]=Math.abs(start-visit[i]);
                queue[nearIndex]=-1;
                start=nearNum;
                nearNum=9999;
            }
        }
    }


    public void print(int visit[],int start){
        double sum=0;
        System.out.print("访问序列：");
        for(int i=0;i<visit.length;i++){
            System.out.print(visit[i]+" ");
            sum=Math.abs(visit[i]-start)+sum;
            start=visit[i];
        }
        System.out.println();
        System.out.print("移动距离为：");
        for(int i=0;i<visit.length;i++){
            System.out.print(distance[i]+" ");
        }
        System.out.println();
        System.out.println("经过的磁道总数："+sum);
        System.out.println("平均寻道长度："+sum/visit.length);
    }
}

class rootSCAN{
    public int visit[];
    public int nearIndex=0;
    public int distance[];

    public void rootscan(int queue[],int start){
        int nearNum=9999;
        int index=0;
        int direction=1;
        int k=0;
        visit=new int[queue.length];
        distance=new int[queue.length];
        for(int i=0;i<queue.length;i++){
            index=-1;
            for(int j=0;j<queue.length;j++){
                if(queue[j]!=-1){
                    if((direction==1)&&(queue[j]>start)&&(Math.abs(nearNum-start)>Math.abs(queue[j]-start))&&(k==0)){
                        nearNum=queue[j];
                        nearIndex=j;
                        index=0;
                        k=0;
                    }
                    else if((direction==1)&&(Math.abs(nearNum-0)>Math.abs(queue[j]-0))&&(k==-1)){
                        nearNum=queue[j];
                        nearIndex=j;
                        index=0;
                    }
                }
            }
            if((direction==1)&&(index==-1)){
                k=-1;
                i=i-1;
            }
            if(index==0){
                visit[i]=nearNum;
                distance[i]=Math.abs(start-visit[i]);
                queue[nearIndex]=-1;
                start=nearNum;
                nearNum=9999;
            }
        }
    }


    public void print(int visit[],int start){
        double sum=0;
        System.out.print("访问序列：");
        for(int i=0;i<visit.length;i++){
            System.out.print(visit[i]+" ");
            sum=Math.abs(visit[i]-start)+sum;
            start=visit[i];
        }
        System.out.println();
        System.out.print("移动距离为：");
        for(int i=0;i<visit.length;i++){
            System.out.print(distance[i]+" ");
        }
        System.out.println();
        System.out.println("经过的磁道总数："+sum);
        System.out.println("平均寻道长度："+sum/visit.length);
    }
}

public class Test{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        System.out.println("请输入磁盘请求序列长度：");
        int a=sc.nextInt();
        System.out.println("请输入磁盘请求访问序列：");
        int[] queue=new int[a];
        int[] queue1=new int[a];
        int[] queue2=new int[a];
        int[] queue3=new int[a];
        for(int i=0;i<a;i++){
            queue[i]=sc.nextInt();
        }
        for(int i=0;i<a;i++){
            queue1[i]=queue[i];
            queue2[i]=queue[i];
            queue3[i]=queue[i];
        }

        System.out.println("请输入读写头起始位置：");
        int start=sc.nextInt();
        System.out.println("磁道增加的方向：（0向磁道号减少的方向移动,1向磁道号增加的方向移动）");
        int direction=sc.nextInt();

        System.out.println("FCFS");
        FCFS fcfs=new FCFS();
        fcfs.fcfs(queue1,start);
        fcfs.print(fcfs.visit,start);

        System.out.println();

        System.out.println("SSTF");
        SSTF sstf=new SSTF();
        sstf.sstf(queue, start);
        sstf.print(sstf.visit,start);

        System.out.println();

        System.out.println("SCAN");
        SCAN scan=new SCAN();
        scan.scan(queue2,start,direction);
        scan.print(scan.visit,start);

        System.out.println();

        System.out.println("rootSCAN");
        rootSCAN rootscan=new rootSCAN();
        rootscan.rootscan(queue3,start);
        rootscan.print(rootscan.visit,start);
    }
}
